/*
 * @lc app=leetcode.cn id=28 lang=javascript
 *
 * [28] 找出字符串中第一个匹配项的下标
 */

// @lc code=start
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  const m = haystack.length;
  const n = needle.length;
  // KMP算法
  const next = new Array(needle.length);
  // 构造next数组
  next[0] = -1;
  let i = 0;
  let j = -1;
  while (i < n) {
    if (j === -1 || needle[i] === needle[j]) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  // 开始匹配
  i = 0;
  j = 0;
  while (i < m && j < n) {
    if (j === -1 || haystack[i] === needle[j]) {
      if (j === n - 1) return i - n + 1;
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  return -1;
};
// @lc code=end
